package Algorithm.kruskal;

import java.util.Arrays;

//kurskal 算法，解决连通图的最小生成树问题
public class KurskalAlgorithm {

	//表示无穷大的值，表示两个点不连通
	private static final int INF = Integer.MAX_VALUE;
	//边的个数
	private int edgeNum;
	//顶点数组
	private char[] vertexts;
	//邻接矩阵
	private int[][] matrix;
	public static edge[] edges;

	public static void main(String[] args) {
		char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		//设置邻接矩阵,用 INF 表示两点距离很大，不连通
		int[][] matrix = {{0, 5, 7, INF, INF, INF, 2},
				{5, 0, INF, 9, INF, INF, 3},
				{7, INF, 0, INF, 8, INF, INF},
				{INF, 9, INF, 0, INF, 4, INF},
				{INF, INF, 8, INF, 0, 5, 4},
				{INF, INF, INF, 4, 5, 0, 6},
				{2, 3, INF, INF, 4, 6, 0}};

//        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//        //设置邻接矩阵,用 INF 表示两点距离无穷大，不连通；自己到自己距离为0
//        int[][] matrix = {{0, 12, INF, INF, INF, 16, 14},
//                          {12, 0, 10, INF, INF, 7, INF},
//                          {INF, 10, 0, 3, 5, 6, INF},
//                          {INF, INF, 3, 0, 4, INF, INF},
//                          {INF, INF, 5, 4, 0, 2, 8},
//                          {16, 7, 6, INF, 2, 0, 9},
//                          {14, INF, INF, INF, 8, 9, 0}};

		KurskalAlgorithm kurskalAlgorithm = new KurskalAlgorithm(vertexs, matrix);
		kurskalAlgorithm.showMatrix();

		kurskalAlgorithm.kurskal();
	}

	public KurskalAlgorithm(char[] vertexts, int[][] matrix) {
		int index = 0;
		edges = new edge[(vertexts.length - 1) * (vertexts.length - 1) / 2];
		//初始化顶点数和边数
		int vertexLen = vertexts.length;

		//初始化顶点
		this.vertexts = new char[vertexLen];
		for (int i = 0; i < vertexLen; i++) {
			this.vertexts[i] = vertexts[i];
		}

		//初始化边
		this.matrix = new int[vertexLen][vertexLen];
		for (int i = 0; i < vertexLen; i++) {
			for (int j = 0; j < vertexLen; j++) {
				this.matrix[i][j] = matrix[i][j];
			}
		}

		//统计边,获取图中所有的边，放入 edge 数组中，后面需要遍历该数组
		for (int i = 0; i < vertexts.length; i++) {
			for (int j = i + 1; j < vertexts.length; j++) {
				if (matrix[i][j] != INF) {
					edgeNum++;
					edges[index++] = new edge(vertexts[i], vertexts[j], matrix[i][j]);
				}
			}
		}
	}

	public void showMatrix() {
//        System.out.println("邻接矩阵为：");
//        for (int[] line : matrix){
//            System.out.println(Arrays.toString(line));
//        }
//        System.out.println();
		for (int i = 0; i < vertexts.length; i++) {
			for (int j = 0; j < vertexts.length; j++) {
				System.out.printf("%11d", matrix[i][j]);
			}
			System.out.println();
		}
	}

	/**
	 * 对边进行排序处理(冒泡)
	 *
	 * @param edges 边的集合
	 */
	public void sortEdges(edge[] edges) {
		for (int i = 0; i < edges.length - 1; i++) {
			for (int j = 0; j < edges.length - 1; j++) {
				if (edges[j + 1] == null) {
					break;
				}
				if (edges[j].weight > edges[j + 1].weight) {
					edge temp = edges[j];
					edges[j] = edges[j + 1];
					edges[j + 1] = temp;
				}
			}
		}
	}

	/**
	 * 传入顶点的值，返回对应的下标
	 *
	 * @param ch 顶点的值
	 * @return 对应的下标，若找不到返回-1
	 */
	public int getPosition(char ch) {
		for (int i = 0; i < vertexts.length; i++) {
			if (vertexts[i] == ch) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 获取下标为 i 的顶点的 终点
	 * 用于判断两个顶点的终点是否相同
	 *
	 * @param ends
	 * @param i
	 * @return
	 */
	public int getEnd(int[] ends, int i) {
		while (ends[i] != 0) {
			i = ends[i];
		}
		return i;
	}

	// kurskal 算法 =================================
	public void kurskal() {
		//表示最后结果数组的索引，
		int index = 0;
		//用于保存（已有最小生成树）中的每个顶点在最小生成树中的终点
		int[] ends = new int[edgeNum];
		//创建结果数组
		edge[] results = new edge[vertexts.length - 1];

		//获取图中所有边的集合,并排序
		sortEdges(edges);
//        edge[] edges2 = new edge[edgeNum];
//        for (int i = 0; i < edgeNum; i++){
//            edges2[i] = edges[i];
//        }

		//遍历 edges 数组,将边添加到最小生成树中，判断待加入的边是否会形成回路
		//若没有，加入结果集；若有不加入
		// index < vertexts.length-1 表示（结果集合中的边的个数）小于（节点数-1）
		// 若不小于则表示已经解已经找全
		for (int i = 0; i < edgeNum && index < vertexts.length - 1; i++) {
			//获取第 i 条边的 起点 的下标
			int p1 = getPosition(edges[i].start);
			//获取第 i 条边的 终点 的下标
			int p2 = getPosition(edges[i].end);

			//获取 p1 顶点在(已有的最小生成树)中的终点
			int m1 = getEnd(ends, p1);
			//获取 p1 顶点在(已有的最小生成树)中的终点
			int m2 = getEnd(ends, p2);

			//判断是否会构成回路
			if (m1 != m2) {//不相同，不构成回路
				//设置 m1 在已有生成树中的终点
				ends[m1] = m2;
				//把这个边加入结果
				System.out.println(edges[i]);
				results[index++] = edges[i];
			}
		}
		System.out.println(Arrays.toString(results));

	}

	//==============================================

}

//创建一个边的类，该对象实例就表示一条边
class edge {
	//边的两个端点，边的起点
	char start;
	//边的终点
	char end;
	//边的权值
	int weight;

	public edge(char start, char end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}

	@Override
	public String toString() {
		return "<" + start +
				"," + end +
				"," + weight +
				'>';
	}
}
